package com.leetcode.sorts.linked;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author: WuPeng
 * @Date: 2021/5/26 4:38 下午
 *
 * 234: 回文链表
 * 请判断一个链表是否为回文链表。
 *
 * 示例 1:
 *      输入: 1->2
 *      输出: false
 * 示例 2:
 *      输入: 1->2->2->1
 *      输出: true
 * 进阶：
 *      你能否用O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
 *
 */
public class PalindromeLinked_234 {

    public static boolean solution_01(ListNode head){
        Deque<Integer> deque = new LinkedList<>();
        ListNode curr = head;
        while (curr != null){
            deque.push(curr.val);
            curr = curr.next;
        }

        ListNode tmp = head;
        while (tmp != null){
            if (tmp.val != deque.pop()){
                return false;
            }
            tmp = tmp.next;
        }
        return true;
    }

    public static boolean solution_02(ListNode head){
        ListNode slow = head, fast = head;
        ListNode curr, pre = null;

        while (fast != null && fast.next != null){
            curr = slow;
            slow = slow.next;
            fast = fast.next.next;
            curr.next = pre;
            pre = curr;
        }
        if (fast != null){
            slow = slow.next;
        }
        while (pre != null && slow != null){
            if (pre.val != slow.val){
                return false;
            }
            pre  = pre.next;
            slow = slow.next;
        }
        return true;
    }

    public static void main(String[] args) {
        ListNode head  = new ListNode(1);
        ListNode node1 = new ListNode(2);
        ListNode node2 = new ListNode(3);
        ListNode node3 = new ListNode(4);
        ListNode node4 = new ListNode(3);
        ListNode node5 = new ListNode(2);
        ListNode node6 = new ListNode(1);
        head.next  = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;

        boolean flag1 = solution_01(head);
        boolean flag2 = solution_01(head);
        System.out.println(flag1);
        System.out.println(flag2);
    }

}
